import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 字符串的排列 {

    /*
    https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&ru=/exam/oj

    看数据量可以知道是靠dfs, 我是直接HashSet进行去重, 但是还是差点超时, 应该有更好的方法, 还没想到
     */

    public static StringBuilder path;
    public static Set<String> set;
    public static int n;
    public static boolean[] vis;
    public static char[] s;
    public ArrayList<String> Permutation (String str) {
        // write code here
        set = new HashSet<String>();
        path = new StringBuilder();
        n = str.length();
        vis = new boolean[n];
        s = str.toCharArray();
        dfs(0);
        ArrayList<String> ret = new ArrayList<String>(set);
        return ret;
    }

    private void dfs(int pos){
        if(pos == n){
            String ss = path.toString();
            if(!set.contains(ss)){
                set.add(ss);
            }
        }
        for(int i = 0;i < n;i++){
            if(vis[i]){
                continue;
            }
            vis[i] = true;
            path.append(s[i]);
            dfs(pos + 1);
            vis[i] = false;
            path.deleteCharAt(pos);
        }
    }
}
